#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> ballGame(int num, vector<string>& plate)
    {
        int m = plate.size();
        int n = plate[0].size();

        for (int i = 1; i < n - 1; ++i)
        {
            if (plate[0][i] == '.' && check(plate, 0, i, 3, 3, m, n, num)) {
                _ans.push_back({ 0, i });
            }

            if (plate[m - 1][i] == '.' && check(plate, m - 1, i, 1, 1, m, n, num)) {
                _ans.push_back({ m - 1, i });
            }
        }

        for (int i = 1; i < m - 1; ++i)
        {
            if (plate[i][0] == '.' && check(plate, i, 0, 2, 2, m, n, num)) {
                _ans.push_back({ i, 0 });
            }

            if (plate[i][n - 1] == '.' && check(plate, i, n - 1, 0, 0, m, n, num)) {
                _ans.push_back({ i, n - 1 });
            }
        }

        return _ans;
    }

private:
    bool check(const std::vector<std::string>& plate, int posx, int posy, int dirx, int diry, int m, int n, int num)
    {
        int step = 0;
        while (posx >= 0 && posx < m && posy >= 0 && posy < n)
        {
            if (step > num)
            {
                return false;
            }

            if (plate[posx][posy] == 'O')
            {
                return true;
            }

            if (plate[posx][posy] == 'W')
            {
                dirx = (dirx - 1 + 4) % 4;
                diry = (diry - 1 + 4) % 4;
            }
            else if (plate[posx][posy] == 'E')
            {
                dirx = (dirx + 1) % 4;
                diry = (diry + 1) % 4;
            }

            posx += _dirx[dirx];
            posy += _diry[diry];
            ++step;
        }

        return false;
    }

    std::vector<int> _dirx = { 0,-1,0,1 };
    std::vector<int> _diry = { -1,0,1,0 };
    std::vector<std::vector<int>> _ans;
};